{
 "cells": [
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "### 拼数\n",
    "    给定n个正整数a1,a2,…，你可以将它们任意排序。现要将这n个数字连接成一排，即令相邻数字收尾相接，组成一个数。问，这个数最大可以是多少。\n",
    "    输入格式\n",
    "    第一行输入一个正整数n（1≤n≤20）。第二行输入n个正整数a1,a2...an\n",
    "    输出格式\n",
    "    输出一个整数，表示答案。"
   ],
   "id": "9d72c289bddcdad5"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-11T04:47:17.492157Z",
     "start_time": "2025-03-11T04:47:00.947069Z"
    }
   },
   "cell_type": "code",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "34331312\n"
     ]
    }
   ],
   "source": "",
   "id": "f17c9794149f8603",
   "execution_count": null
  },
  {
   "cell_type": "code",
   "id": "initial_id",
   "metadata": {
    "collapsed": true,
    "ExecuteTime": {
     "end_time": "2025-03-09T06:20:42.866686Z",
     "start_time": "2025-03-09T06:20:33.623843Z"
    }
   },
   "source": [
    "from ctypes import create_unicode_buffer\n",
    "\n",
    "n=int(input())\n",
    "nums=input().split()\n",
    "for i in range(len(nums)-1):\n",
    "    for j in range(i+1,len(nums)):\n",
    "        if nums[i]+nums[j]<nums[j]+nums[i]:#此处是字符串拼接之后的大小比较，大的放前面\n",
    "            nums[i],nums[j]=nums[j],nums[i]\n",
    "print(''.join(nums))\n",
    "        \n"
   ],
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "34331213\n"
     ]
    }
   ],
   "execution_count": 1
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "### 小蓝爱串串\n",
    "    老师现在有n个长度为m的仅有小写字母组成的字符串，请小蓝将n个字符串拼接成一个串，且这个串字典序最小。\n",
    "    输入格式\n",
    "    第一行两个正整数n,m ，代表字符串的数目和长度。接下来输入n行，每行一个长度为m的字符串。\n",
    "    输出格式\n",
    "    输出一行一个字符串。"
   ],
   "id": "8ab97e02ef15faf1"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-11T04:52:10.878358Z",
     "start_time": "2025-03-11T04:51:59.136930Z"
    }
   },
   "cell_type": "code",
   "source": "",
   "id": "9620fbc151f097eb",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iaoliuyux"
     ]
    }
   ],
   "execution_count": 47
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-09T06:54:10.098483Z",
     "start_time": "2025-03-09T06:53:56.644454Z"
    }
   },
   "cell_type": "code",
   "source": [
    "#字典序->sort sorted\n",
    "n,m=map(int,input().split())\n",
    "list1=[]\n",
    "for i in range(n):\n",
    "    list1.append(input())\n",
    "list1.sort()\n",
    "for i in list1:\n",
    "    print(i,end='')\n"
   ],
   "id": "599166e025c3a445",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "abbcgf"
     ]
    }
   ],
   "execution_count": 6
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-09T06:38:49.959794Z",
     "start_time": "2025-03-09T06:38:49.948909Z"
    }
   },
   "cell_type": "code",
   "source": [
    "list1=['abc','sed','ert']\n",
    "for i in list1:\n",
    "    print(i,end='')"
   ],
   "id": "14e50ab31d9d6794",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "abcsedert"
     ]
    }
   ],
   "execution_count": 3
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "### 劈瓜\n",
    "    西瓜一共有n个，其中第i个西瓜的重量为wi千克 ，西瓜的单价是1千克/元。小菌想要买尽可能多个的西瓜，但是他手头只有m元钱。为了防止西瓜切开导致变质速度加快，瓜老板最多允许你劈一个瓜，他有一个高科技切瓜机，一定可以将瓜平均分为两半。请你帮他计算一下，最多可以买下几个西瓜，小数点后保留一位小数。\n",
    "    输入格式\n",
    "    第1行输入两个正整数n,m表示西瓜的个数及小菌手头的钱数。第2行输入n个正整数w1,w2,w3,…,wn，表示所有瓜的重量。\n",
    "    输出格式\n",
    "    输出数据共一行为一个浮点数，表示小菌最多可以买下西瓜的数量。"
   ],
   "id": "84d57a194c4a077e"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-09T08:04:08.511263Z",
     "start_time": "2025-03-09T08:04:02.577161Z"
    }
   },
   "cell_type": "code",
   "source": [
    "#这个题感觉可对就是结果错误烦人。ai修改了一番，思路还是一样的\n",
    "n,m=map(int,input().split())\n",
    "weight=list(map(int,input().split()))\n",
    "count=0#买西瓜的数量\n",
    "total=0#总重量\n",
    "weight.sort()\n",
    "for i in weight:\n",
    "    if total+i<total:\n",
    "        total+=i\n",
    "        count+=1\n",
    "    else:\n",
    "        break\n",
    "#判断半个瓜\n",
    "if count<n and total+weight[count]/2<=m:\n",
    "    count+=(1/2)\n",
    "print(f\"{count:.1f}\")"
   ],
   "id": "6aaf6ae5caa8bd7a",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.5\n"
     ]
    }
   ],
   "execution_count": 13
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "### 实现选择排序\n",
    "    介绍如下：\n",
    "    选择排序的工作原理是每一次从需要排序的数据元素中选出最小的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排列完毕。请编写代码，完成选择排序，对给定数据进行升序排\n",
    "    输入描述\n",
    "    第一行，数字N(2≤N≤100),表示待排序的元素个数。第二行，待排序的元素。\n",
    "    输出描述\n",
    "    输出一行，为升序序列。"
   ],
   "id": "fb266822085e9639"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-11T04:59:50.171190Z",
     "start_time": "2025-03-11T04:59:36.736635Z"
    }
   },
   "cell_type": "code",
   "source": "",
   "id": "61986aedf10bd6cc",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 12 15\n"
     ]
    }
   ],
   "execution_count": 50
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-10T07:52:37.230458Z",
     "start_time": "2025-03-10T07:52:28.813034Z"
    }
   },
   "cell_type": "code",
   "source": [
    "N=int(input())\n",
    "l=list(map(int,input().split()))\n",
    "def select_sort(li):  #选择排序：第一个与最小的交换位置\n",
    "    for i in range(N):\n",
    "        min_index=i  #待排的第一个\n",
    "        for j in range(i,N):\n",
    "            if li[min_index]>li[j]:\n",
    "                min_index=j  #与小的交换位置\n",
    "        li[min_index],li[i]=li[i],li[min_index]#i与后面待排的最小的交换位置\n",
    "    return li\n",
    "select_sort(l)\n",
    "# print(*l)  *解包 相当于  ↓\n",
    "for m in l:\n",
    "    print(m,end=' ')\n"
   ],
   "id": "59db08bed3d2638a",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 4 5 7 8 "
     ]
    }
   ],
   "execution_count": 17
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "### 插入排序\n",
   "id": "e5cab4e0397102d1"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-11T05:11:26.731298Z",
     "start_time": "2025-03-11T05:11:14.432367Z"
    }
   },
   "cell_type": "code",
   "source": "",
   "id": "caeed7df34970194",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 4 5 7 8\n"
     ]
    }
   ],
   "execution_count": 60
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-11T05:08:29.273812Z",
     "start_time": "2025-03-11T05:08:21.845233Z"
    }
   },
   "cell_type": "code",
   "source": [
    "n=int(input())\n",
    "l=list(map(int,input().split()))\n",
    "\n",
    "def insert_sort(li):\n",
    "    for i in range(1,n):\n",
    "        key=li[i]#需要排序的数\n",
    "        j=i-1#排好序的最后一个数\n",
    "        while j>=0:\n",
    "            if li[j]>key:\n",
    "                li[j+1]=li[j]  #数大了就往后挪位置腾地方\n",
    "                li[j]=key\n",
    "            j-=1\n",
    "    return li\n",
    "insert_sort(l)\n",
    "print(*l)"
   ],
   "id": "628bc491defde3b8",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 4 5 7 8\n"
     ]
    }
   ],
   "execution_count": 56
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "",
   "id": "d4646dcd91d10f12"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "### 快速排序\n",
    "    快速排序的工作原理是通过一次排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。"
   ],
   "id": "7643b18b806081bc"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-11T05:16:26.011595Z",
     "start_time": "2025-03-11T05:16:14.043274Z"
    }
   },
   "cell_type": "code",
   "source": "",
   "id": "1556f5b6c7539482",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 4 5 7 8\n"
     ]
    }
   ],
   "execution_count": 63
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-10T08:55:57.396260Z",
     "start_time": "2025-03-10T08:55:49.400813Z"
    }
   },
   "cell_type": "code",
   "source": [
    "n=int(input())\n",
    "l=list(map(int,input().split()))\n",
    "def quick_sort(li):\n",
    "    if len(li)<=1:\n",
    "        return li\n",
    "    pivot=li[0] #基准元素\n",
    "    left=[]\n",
    "    right=[]\n",
    "    for i in li[1:]:\n",
    "        if i<=pivot:\n",
    "            left.append(i)\n",
    "        else:\n",
    "            right.append(i)\n",
    "    return quick_sort(left)+[pivot]+quick_sort(right)\n",
    "#返回的并不是原数组，所以要接收排序后的结果\n",
    "sorted_li=quick_sort(l)\n",
    "print(*sorted_li)"
   ],
   "id": "d35c505bd64711f2",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 4 5 7 8\n"
     ]
    }
   ],
   "execution_count": 19
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "### 归并排序\n",
    "    1.将待排序的线数据不断地切分成若干个部分，直到每个部分只包含一个元素，这时，可以认为只包含一个元素的序列是有序的。\n",
    "    2.将切分后的数据两两合并，每合并一次，就会产生一个新的且更长的有序序列，重复这一步骤，直到最后只剩下一个序列，这个序列就是排好序的数据。"
   ],
   "id": "d00a68ce0adc5724"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-10T10:14:33.150343Z",
     "start_time": "2025-03-10T10:14:23.066718Z"
    }
   },
   "cell_type": "code",
   "source": [
    "n=int(input())\n",
    "l=list(map(int,input().split()))\n",
    "\n",
    "def merge(left,right):\n",
    "    merged=[]\n",
    "    i=j=0\n",
    "    while i<len(left) and j<len(right):  ##i,j这里是索引(0,len(list)),不能加等号，不然超出范围了\n",
    "        if left[i]<=right[j]:\n",
    "            merged.append(left[i])\n",
    "            i+=1\n",
    "        else:\n",
    "            merged.append(right[j])\n",
    "            j+=1\n",
    "        #while循环结束剩余的元素\n",
    "    merged+=left[i:]#left和right中的剩余的\n",
    "    merged+=right[j:]\n",
    "    return merged\n",
    "    \n",
    "def merge_sort(li):\n",
    "    if len(li)<=1:\n",
    "        return li\n",
    "    mid=len(li)//2\n",
    "    left=merge_sort(li[:mid])\n",
    "    right=merge_sort(li[mid:])\n",
    "    return merge(left,right)\n",
    "\n",
    "sorted=merge_sort(l)\n",
    "print(*sorted)\n",
    "    \n",
    "    "
   ],
   "id": "41d51996ffc766cc",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 4 5 7 8\n"
     ]
    }
   ],
   "execution_count": 32
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "### 基数排序\n",
    "    实现基数排序算法。基数排序的介绍如下：\n",
    "    1.将整数按位数切割,然后将数值统一为同样的数位长度，数位较短的数前面补零。\n",
    "    2.从最低位开始，依次进行一次排序。\n",
    "    3.从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列"
   ],
   "id": "49f6312bef5ebd9b"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-10T12:09:18.865255Z",
     "start_time": "2025-03-10T12:09:11.177828Z"
    }
   },
   "cell_type": "code",
   "source": [
    "#这个再看看咯\n",
    "n=int(input())\n",
    "l=list(map(int,input().split()))\n",
    "#初始化桶  len(str(max(L))) 桶最大子数量\n",
    "buct=[[] for _ in range(len(str(max(l))))]\n",
    "\n",
    "#将列表 L 中的每个数字根据其位数分配到不同的桶中。\n",
    "for i in range(n):\n",
    "    buct[len(str(i))-1].append(l[i])\n",
    " #对每个桶中的数字进行排序\n",
    "for i in buct:\n",
    "    i.sort()\n",
    "result=[]\n",
    "for i in buct:\n",
    "    result+=i\n",
    "print(*result)"
   ],
   "id": "dfb8117e697c8f8",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 4 5 7 8\n"
     ]
    }
   ],
   "execution_count": 34
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-11T07:19:55.781842Z",
     "start_time": "2025-03-11T07:19:55.762871Z"
    }
   },
   "cell_type": "code",
   "source": [
    "A=[1,2,3,None,None]\n",
    "print(len(A))"
   ],
   "id": "1c631c65eed91976",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "execution_count": 64
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
